package LeetCode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}9:58
 */
public class LeetCode131 {
    List<List<String>> res = new ArrayList<>();
    public List<List<String>> partition(String s) {
        if (s == null || s.equals("")){
            return res;
        }
        int len = s.length();
        //必须使用一个数据结构来装递归树的一条分支路线
        List<String> list = new ArrayList<>();
        //加上记忆集 来进行回文的判断
        // 预处理
        // 状态：dp[i][j] 表示 s[i][j] 是否是回文
        boolean[][] dp = new boolean[len][len];
        // 状态转移方程：在 s[i] == s[j] 的时候，dp[i][j] 参考 dp[i + 1][j - 1]
        for (int right = 0; right < len; right++) {
            // 注意：left <= right 取等号表示 1 个字符的时候也需要判断
            for (int left = 0; left <= right; left++) {
                if (s.charAt(left) == s.charAt(right) && (right - left <= 2 || dp[left + 1][right - 1])) {
                    dp[left][right] = true;
                }
            }
        }
        backtracking(s,0,len,list,dp);
//        backtracking(s,0,s.length(),list);
        return res;
    }

    public void backtracking(String s,int start,int len,List<String> list){
        // 递归跳出条件
        if (start == len){
            res.add(new ArrayList<>(list));
            return;
        }

        for (int i = start; i < len; i++){
            //进行回文的判断
            if (!checkPalindrome(s,start,i)){
                continue;
            }
            list.add(s.substring(start,i + 1));
            backtracking(s,i + 1,len,list);
            list.remove(list.size() - 1);
        }
    }

    public void backtracking(String s,int start,int len,List<String> list,boolean[][] dp){
        if (start == len){
            res.add(new ArrayList<>(list));
            return;
        }

        for (int i = start; i < len; i++){
            if (!dp[start][i]){
                continue;
            }
            list.add(s.substring(start,i + 1));
            backtracking(s,i + 1,len,list,dp);
            list.remove(list.size() - 1);
        }
    }

    private boolean checkPalindrome(String s, int left, int right) {
        while(left < right){
            if (s.charAt(left++) != s.charAt(right--)){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(new LeetCode131().partition("aab").toString());
    }
}
